This invention relates to LSI layout design technology in the design of large scale integrated (LSI) circuits. It relates particularly to an LSI layout design method capable of meeting timing constraints.
In the layout design of an LSI circuit for use by high-performance information apparatus, a placement of cells is carried out in order of meeting timing constraints which assure the fast clock operation of sync circuits. Such placement, known in the art as a "timing driven placement" becomes important in the layout design of LSI circuits.
A typical timing driven placement method is described. A term for evaluation of the length of a connection line relating to a signal path with the maximum delay (i.e., a critical path) of signal paths in a combinational circuit that has an effect on timing, is added to a function of placement evaluation for circuit area and connection line length evaluation, and the placement of cell is repeatedly improved to minimize the function of placement evaluation.
The above-described method is problematic. In the conventional method, not only timing but also circuit area is evaluated. This will not give a sure guarantee that the timing constraints are satisfied, therefore leading to producing an undesirable placement result with a partial timing constraints violation. Accordingly, in order to meet the timing constraints without fail, it is necessary to repeat a logic design by, for example, re-synthesis after a layout design is carried out.
Since a meticulous placement improvement must be performed to obtain an optimal placement result, associated processing is a time consuming process. It is difficult to improve the efficiency of LSI design.
The inventors of the present invention devised the following method to provide a solution to the problem with the prior art.
Whether timing constraints are satisfied or not is determined by cell placement and wiring between flip-flops that are a critical path beginning and a critical path end, respectively. The inventors paid attention to this point. Connections among flip-flops relating to the timing constraints are found in advance. Subsequently, placement locations for the flip-flops are determined for optimal timing and a layout design is then carried out. In accordance with this method, instead of performing a layout design of a huge number of cells forming an LSI circuit at a time, a layout design of a less number of flip-flops is carried out. This seems to promise not only a considerable reduction of the processing time but also a layout which does meet the timing constraints.
However, the finding of connections among flip-flops relating to the timing constraints is not easy, and it is difficult to represent the found connections in computer readable form.
For example, a case, in which connections among flip-flops are found from a logical-level netlist shown in FIG. 13(a), is explained. In such a case, the found connections will be given in the form of an approximately complete graph, i.e., in the form of a graph in which each node branches out to all the remaining other nodes (see FIG. 13(b)), for a single combinational circuit provides signals to various flip-flops. For this reason, even when trying to determine a placement location for each of the flip-flops for optimal timing, it is not possible to do so.
The fact that the connections form an approximately complete graph means that each flip-flop is in signal input/output relationship with almost all the other flip-flops. On the other hand, for the timing constraints to be met, it is necessary to place flip-flops, which are a signal flow beginning and a signal flow end, in close proximity with each other. For this reason, if the connections (connection relationship) is approximately a complete graph, this makes it possible to bring the flip-flops in close proximity with each other. However, since areas near the flip-flops are finite, this will not guarantee that every flip-flop is placed at its optimal placement location. Accordingly, it is important that the connections will not take an approximately complete graph form.